package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder

/**
 *
 * 题型：二叉树的中序遍历、后序遍历，分割数组
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
 */
class leetcode_106 {
    @Test
    fun test_1() {
        val root = buildTree(intArrayOf(9, 3, 15, 20, 7), intArrayOf(9, 15, 7, 20, 3))
        val actual = printLevelOrder(root)
        val expect = arrayListOf(arrayListOf(3), arrayListOf(9, 20), arrayListOf(15, 7))
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    @Test
    fun test_2() {
        val root = buildTree(intArrayOf(-1), intArrayOf(-1))
        val actual = printLevelOrder(root)
        val expect = arrayListOf(arrayListOf(-1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {
        // T - N的平方
        // S - N

        // 中序数组
        // 后序数组
        // 第1步：后序数组的大小为0，则为空节点。返回它
        // 第2步：取后序数组的最后一个元素作为节点。如果size 为1，则返回该节点
        // 第3步：找到后序数组的最后一个元素在中序数组的位置，作为切割点
        // 第4步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
        // 第5步：切割后序数组，切成后序左数组和后序右数组
        // 第6步：递归处理左区间和右区间
        // 注意区间的闭合：使用[)

        // 简写
        // step 1 : size 0
        // step 2 ：head = 后序数组[N] (size 1 or > 1）
        // step 3 : index head at 中序
        // step 4 : 切割中序数组
        // step 5 : 切割后序数组
        // step 6 ： 递归处理左右区间

        // step 1 : size 0
        if (postorder.size == 0) { // TODO:这一点不同
            return null
        }
        // step 2 ：head = 后序数组[N] (if size 1 return）
        val n: Int = postorder[postorder.size - 1] // TODO:这一点不同
        val node = TreeNode(n)
        if (postorder.size == 1) {
            return node
        }

        // step 3 : index head at 中序
        var index: Int = 0
        for (i in 0..inorder.size - 1) {
            if (inorder[i] == n) {
                index = i
                break
            }
        }

        // step 4 : 切割中序数组
        val left1: IntArray = inorder.sliceArray(0 until index) // [0, index)
//        println("left1=${left1.contentToString()}")
        val right1: IntArray = inorder.sliceArray(index + 1 until inorder.size)  // [index + 1, size)
//        println("right1=${right1.contentToString()}")

        // step 5 : 切割后序数组
        // postorder 舍弃末尾元素
        val postorder: IntArray = postorder.sliceArray(0 until postorder.size - 1)  // [0, end index -1) TODO:这一点不同
        val left2: IntArray = postorder.sliceArray(0 until left1.size) //  [0, leftInorder.size)
//        println("left2=${left2.contentToString()}")
        val right2: IntArray = postorder.sliceArray(left1.size until postorder.size) // [leftInorder.size(), size)
//        println("right2=${right2.contentToString()}")

        // step 6 ： 递归处理左右区间
        node.left = buildTree(left1, left2) // TODO:这一点不同
        node.right = buildTree(right1, right2) // TODO:这一点不同
        return node
    }
}